package com.algorithms.sorts.advances;

import com.algorithms.sorts.Sort;

/**
 * QuickSort<br>
 * Complexity O(N*logN)<br><br>
 * 
 * algorithms:<br>
 * - QuickSort bases on partitioning: an array can be divided into 
 * 2 sub arrays which items from left array smaller than a pivot number
 * while items from right array are bigger.<br>
 * 
 * - after the first step, we run partitioning on each smaller sub
 * array (partitions), until we meet the partition with only 1 item
 * or 2 items.<br><br>
 * 
 * complexity:<br>
 * - the complexity of QuickSort in an arbitrary array is O(N*logN),
 * where partitioning always find the pivot lies around the middle 
 * of array.<br>
 * - in the worst case where left or right sub partition maintains 
 * length around (N - 1) for each time of separation, then the total
 * process steps are O(N^2).
 * 
 * @author minhld
 *
 */
public class QuickSort extends Sort{
	
	public QuickSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "QuickSort";
	}
	
	@Override
	public int[] sort(){
		quickSort(0, this.length - 1);
		return this.data;
	}
	
	private void quickSort(int left, int right){
		if (left >= right) return;
		
		int partPos = partition(left, right);
		
		quickSort(left, partPos);
		quickSort(partPos + 1, right);
		
	}
	
	/**
	 * partition will place all items that value < pivot
	 * to the left side, and all items that value >= pivot
	 * to the right side.
	 * 
	 * @param left
	 * @param right
	 */
	private int partition(int left, int right){
		// find pivot, and also compare and swap left-most
		// and right-most items.
		int pivot = getPivot(left, right);
				
		int leftPtr = left + 1, rightPtr = right - 1;
		
		if (leftPtr == rightPtr){
			this.numOfProcess++;
			
			if (this.data[leftPtr] < pivot){
				return leftPtr;
			}else{
				return --leftPtr;
			}
		}
		
		while (leftPtr < rightPtr){
			// left pointer moves to the position that
			// item value > pivot
			while (this.data[leftPtr] < pivot){
				leftPtr++;
				
				this.numOfProcess++;
			}
			
			// right pointer moves to the position that
			// item value < pivot
			while (this.data[rightPtr] > pivot){
				rightPtr--;
				
				this.numOfProcess++;
			}
			
			// then swap the item at left and right so that
			// they will be place at correct position.
			if (leftPtr < rightPtr){
				swap(leftPtr, rightPtr);
				
				this.numOfCopy += 2;
			}
		}
		
		return leftPtr - 1;
	}
	
	/**
	 * this function is to get pivot value of an array by
	 * using 3 values (left, middle, right).<br> 
	 * this will help to avoid trivial pivot value which 
	 * causes QuickSort to have complexity of O(N^2).<br>
	 * for example if the pivot make the two unproportional 
	 * partitions, and the bigger portition make another same 
	 * two, and so on, it will make the partition process go 
	 * with complexity of O(N), not O(logN).
	 * 		
	 * @param left
	 * @param right
	 * @return
	 */
	private int getPivot(int left, int right){
		this.numOfProcess++;

		if (left == right - 1){
			if (this.data[left] > this.data[right]){
				swap(left, right);

				this.numOfCopy += 2;
			}
			
			return (int)Math.floor((this.data[left] + this.data[right]) / 2);
		}else {
			if (this.data[left] > this.data[right]){
				swap(left, right);
				
				this.numOfCopy += 2;
			}
			
			int middle = (int)Math.floor((right + left) / 2);
			return (int)Math.floor((this.data[left] + this.data[middle] + this.data[right]) / 3);
		}
	}
}
